////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef array_h__
#define array_h__

#include "core/types.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	Array
	///
	/// \brief	Array. 
	///
	/// \todo	Add documentation!
	///
	/// \author	Markus
	/// \date	22.02.2010
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T> 
	class Array
	{
	public:

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \typedef	T* Iterator
		///
		/// \brief	.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		typedef T* Iterator;




		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array()
		///
		/// \brief	Default constructor. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array(tSize initialCapacity, tSize initialGrow)
		///
		/// \brief	Constructor. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	initialCapacity	The initial capacity. 
		/// \param	[in]	initialGrow		The initial grow. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array(tSize initialCapacity, tSize initialGrow);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array(tSize initialSize, tSize initialGrow, const T& initialValue)
		///
		/// \brief	Constructor. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	initialSize		Size of the initial. 
		/// \param	[in]	initialGrow		The initial grow. 
		/// \param	[in]	initialValue	The initial value. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array(tSize initialSize, tSize initialGrow, const T& initialValue);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array(const Array<T>& rhs)
		///
		/// \brief	Constructor. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	rhs	The right hand side. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array(const Array<T>& rhs);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	~Array()
		///
		/// \brief	Finaliser. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		~Array();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void operator=(const Array<T>& rhs)
		///
		/// \brief	Copy operator. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	rhs	The right hand side. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void operator=(const Array<T>& rhs);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	T& operator[](tIndex index) const
		///
		/// \brief	 casting operator. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	index	Zero-based index of the. 
		///
		/// \return	The result of the operation. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		T& operator[](tIndex index) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool operator==(const Array<T>& rhs) const
		///
		/// \brief	Equality operator. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	rhs	The right hand side. 
		///
		/// \return	true if the parameters are considered equivalent. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool operator==(const Array<T>& rhs) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool operator!=(const Array<T>& rhs) const
		///
		/// \brief	Inequality operator. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	rhs	The right hand side. 
		///
		/// \return	true if the parameters are not considered equivalent. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool operator!=(const Array<T>& rhs) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Add(const T& elm)
		///
		/// \brief	Adds elm.
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	The const T& to add. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Add(const T& elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Add(const Array<T>& rhs)
		///
		/// \brief	Adds rhs.
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	rhs	The const Array<T>& to add. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Add(const Array<T>& rhs);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Reserve(tSize num)
		///
		/// \brief	Reserves. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	num	Number of. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Reserve(tSize num);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tSize Size() const
		///
		/// \brief	Sizes this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tSize Size() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tSize Capacity() const
		///
		/// \brief	Capacities this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tSize Capacity() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	T& Front() const
		///
		/// \brief	Fronts this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		T& Front() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	T& Back() const
		///
		/// \brief	Backs this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		T& Back() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool IsEmpty() const
		///
		/// \brief	Query if this object is empty. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	true if empty, false if not. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool IsEmpty() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void EraseIndex(tIndex index)
		///
		/// \brief	Erase index. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	index	Zero-based index of the. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void EraseIndex(tIndex index);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Iterator Erase(Iterator iter)
		///
		/// \brief	Erases. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	iter	The iterator. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Iterator Erase(Iterator iter);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void EraseIndexSwap(tIndex index)
		///
		/// \brief	Erase index swap. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	index	Zero-based index of the. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void EraseIndexSwap(tIndex index);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Iterator EraseSwap(Iterator iter)
		///
		/// \brief	Erase swap. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	iter	The iterator. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Iterator EraseSwap(Iterator iter);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Insert(tIndex index, const T& elm)
		///
		/// \brief	Inserts. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	index	Zero-based index of the. 
		/// \param	[in]	elm		The elm. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Insert(tIndex index, const T& elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tIndex InsertSorted(const T& elm)
		///
		/// \brief	Inserts a sorted described by elm. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	The elm. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tIndex InsertSorted(const T& elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tIndex InsertAtEndOfIdenticalRange(tIndex startIndex, const T& elm)
		///
		/// \brief	Inserts at end of identical range. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	startIndex	The start index. 
		/// \param	[in]	elm			The elm. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tIndex InsertAtEndOfIdenticalRange(tIndex startIndex, const T& elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	bool IsSorted() const
		///
		/// \brief	Query if this object is sorted. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	true if sorted, false if not. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		bool IsSorted() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Clear()
		///
		/// \brief	Clears this object to its blank/initial state. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Clear();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Reset()
		///
		/// \brief	Resets this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Reset();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Iterator Begin() const
		///
		/// \brief	Begins this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Iterator Begin() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Iterator End() const
		///
		/// \brief	Ends this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Iterator End() const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Iterator Find(const T& elm) const
		///
		/// \brief	Finds. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	The elm. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Iterator Find(const T& elm) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tIndex FindIndex(const T& elm) const
		///
		/// \brief	Searches for the first index. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	The elm. 
		///
		/// \return	The found index. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tIndex FindIndex(const T& elm) const;

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Fill(tIndex first, tSize num, const T& elm)
		///
		/// \brief	Fills. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	first	The first. 
		/// \param	[in]	num		Number of. 
		/// \param	[in]	elm		The elm. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Fill(tIndex first, tSize num, const T& elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Realloc(tSize capacity, tSize grow)
		///
		/// \brief	Reallocs. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	capacity	The capacity. 
		/// \param	[in]	grow		The grow. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Realloc(tSize capacity, tSize grow);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	Array<T> Difference(const Array<T>& rhs)
		///
		/// \brief	Differences. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	rhs	The right hand side. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		Array<T> Difference(const Array<T>& rhs);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Sort()
		///
		/// \brief	Sorts this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Sort();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	tIndex BinarySearchIndex(const T& elm) const
		///
		/// \brief	Binary search index. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	The elm. 
		///
		/// \return	. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		tIndex BinarySearchIndex(const T& elm) const;

	private:

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Destroy(T* elm)
		///
		/// \brief	Destroys the given elm. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	elm	If non-null, the T* to destroy. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Destroy(T* elm);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Copy(const Array<T>& src)
		///
		/// \brief	Copies the given src. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	src	Source for the. 
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Copy(const Array<T>& src);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Delete()
		///
		/// \brief	Deletes this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Delete();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Grow()
		///
		/// \brief	Grows this object. 
		///
		/// \author	Markus
		/// \date	22.02.2010
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Grow();

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void GrowTo(tSize newCapacity)
		///
		/// \brief	This extents Array and reallocates it with the specified size.
		///			Thereby no elements of the element will be erased, they will all
		///			be part of the new Array.
		///
		/// \author	Markus
		/// \date	22.02.2010
		///
		/// \param	[in]	newCapacity	The new size the Array should have.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void GrowTo(tSize newCapacity);

		////////////////////////////////////////////////////////////////////////////////////////////////////
		/// \fn	void Move(tIndex fromIndex, tIndex toIndex)
		///
		/// \brief	This moves the element at the first specified index to the second index.
		///			If the second index is begin the bounds we'll try to allocate a new 
		///			Array through the internal grow functions.
		///
		/// \author	Markus
		/// \date	21.02.2010
		///
		/// \param	[in]	fromIndex	The index of the element we want to move.
		/// \param	[in]	toIndex		THe index where to move the element.
		////////////////////////////////////////////////////////////////////////////////////////////////////
		void Move(tIndex fromIndex, tIndex toIndex);




		static const tSize MinGrowSize = 16;
		static const tSize MaxGrowSize = 65536; // FIXME: big grow size needed for mesh tools
		tSize grow;                             // grow by this number of elements if array exhausted
		tSize capacity;                         // number of elements allocated
		tSize size;                             // number of elements in array
		T* elements;                         // pointer to element array
	};

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T>
	Array<T>::Array() :
		grow(8),
		capacity(0),
		size(0),
		elements(0)
	{
		// empty
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T>
	Array<T>::Array(tSize _capacity, tSize _grow) :
		grow(_grow),
		capacity(_capacity),
		size(0)
	{
		if (0 == this->grow)
		{
			this->grow = 16;
		}
		if (this->capacity > 0)
		{
			this->elements = r_narray(T, this->capacity);
		}
		else
		{
			this->elements = 0;
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T>
	Array<T>::Array(tSize initialSize, tSize _grow, const T& initialValue) :
		grow(_grow),
		capacity(initialSize),
		size(initialSize)
	{
		if (0 == this->grow)
		{
			this->grow = 16;
		}
		if (initialSize > 0)
		{
			this->elements = r_narray(T, this->capacity);
			tIndex i;
			for (i = 0; i < initialSize; i++)
			{
				this->elements[i] = initialValue;
			}
		}
		else
		{
			this->elements = 0;
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Copy(const Array<T>& src)
	{
		this->grow = src.grow;
		this->capacity = src.capacity;
		this->size = src.size;
		if (this->capacity > 0)
		{
			this->elements = r_narray(T, this->capacity);
			tIndex i;
			for (i = 0; i < this->size; i++)
			{
				this->elements[i] = src.elements[i];
			}
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Delete()
	{
		this->grow = 0;
		this->capacity = 0;
		this->size = 0;
		if (this->elements)
		{
			r_darray(this->elements);
			this->elements = 0;
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Destroy(T* elm)
	{
		elm->~T();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T>
	Array<T>::Array(const Array<T>& rhs) :
		grow(0),
		capacity(0),
		size(0),
		elements(0)
	{
		this->Copy(rhs);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T>
	Array<T>::~Array()
	{
		this->Delete();
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Realloc(tSize _capacity, tSize _grow)
	{
		this->Delete();
		this->grow = _grow;
		this->capacity = _capacity;
		this->size = 0;
		if (this->capacity > 0)
		{
			this->elements = r_narray(T, this->capacity);
		}
		else
		{
			this->elements = 0;
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void 
	Array<T>::operator=(const Array<T>& rhs)
	{
		if (this != &rhs)
		{
			if ((this->capacity > 0) && (rhs.size <= this->capacity))
			{
				tIndex i;
				for (i = 0; i < rhs.size; i++)
				{
					this->elements[i] = rhs.elements[i];
				}

				// properly destroy remaining original elements
				for (; i < this->size; i++)
				{
					this->Destroy(&(this->elements[i]));
				}
				this->grow = rhs.grow;
				this->size = rhs.size;
			}
			else
			{
				// source array doesn't fit into our capacity, need to reallocate
				this->Delete();
				this->Copy(rhs);
			}
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::GrowTo(tSize newCapacity)
	{
		T* newArray = r_narray(T, newCapacity);
		if (this->elements)
		{
			// copy over contents
			tIndex i;
			for (i = 0; i < this->size; i++)
			{
				newArray[i] = this->elements[i];
			}

			// discard old array and update contents
			r_darray(this->elements);
		}
		this->elements  = newArray;
		this->capacity = newCapacity;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Grow()
	{

		tSize growToSize;
		if (0 == this->capacity)
		{
			growToSize = this->grow;
		}
		else
		{
			// grow by half of the current capacity, but never more then MaxGrowSize
			tSize growBy = this->capacity >> 1;
			if (growBy == 0)
			{
				growBy = MinGrowSize;
			}
			else if (growBy > MaxGrowSize)
			{
				growBy = MaxGrowSize;
			}
			growToSize = this->capacity + growBy;
		}
		this->GrowTo(growToSize);
	}

	//------------------------------------------------------------------------------
	/**
		30-Jan-03   floh    serious bugfixes!
		07-Dec-04	jo		bugfix: neededSize >= this->capacity => neededSize > capacity	
	*/
	template<class T> void
	Array<T>::Move(tIndex fromIndex, tIndex toIndex)
	{

		// nothing to move?
		if (fromIndex == toIndex)
		{
			return;
		}

		// compute number of elements to move
		tSize num = this->size - fromIndex;

		// check if array needs to grow
		tSize neededSize = toIndex + num;
		while (neededSize > this->capacity)
		{
			this->Grow();
		}

		if (fromIndex > toIndex)
		{
			// this is a backward move
			tIndex i;
			for (i = 0; i < num; i++)
			{
				this->elements[toIndex + i] = this->elements[fromIndex + i];
			}

			// destroy remaining elements
			for (i = (fromIndex + i) - 1; i < this->size; i++)
			{
				this->Destroy(&(this->elements[i]));
			}
		}
		else
		{
			// this is a forward move
			int i;  // NOTE: this must remain signed for the following loop to work!!!
			for (i = num - 1; i >= 0; --i)
			{
				this->elements[toIndex + i] = this->elements[fromIndex + i];
			}

			// destroy freed elements
			for (i = int(fromIndex); i < int(toIndex); i++)
			{
				this->Destroy(&(this->elements[i]));
			}
		}

		// adjust array size
		this->size = toIndex + num;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Add(const T& elm)
	{
		// grow allocated space if exhausted
		if (this->size == this->capacity)
		{
			this->Grow();
		}

		this->elements[this->size++] = elm;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Add(const Array<T>& rhs)
	{
		tIndex i;
		tSize num = rhs.Size();
		for (i = 0; i < num; i++)
		{
			this->Add(rhs[i]);
		}
	}

	//------------------------------------------------------------------------------
	/**
		This increases the capacity to make room for N elements. If the
		number of elements is known before appending the elements, this 
		method can be used to prevent reallocation. If there is already
		enough room for N more elements, nothing will happen.
	    
		NOTE: the functionality of this method has been changed as of 26-Apr-08,
		it will now only change the capacity of the array, not its size.
	*/
	template<class T> void
	Array<T>::Reserve(tSize num)
	{
		tSize neededCapacity = this->size + num;
		if (neededCapacity > this->capacity)
		{
			this->GrowTo(neededCapacity);
		}
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> tSize
	Array<T>::Size() const
	{
		return this->size;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> tSize
	Array<T>::Capacity() const
	{
		return this->capacity;
	}

	//------------------------------------------------------------------------------
	/**
		Access an element. This method will NOT grow the array, and instead do
		a range check, which may throw an assertion.
	*/
	template<class T> T&
	Array<T>::operator[](tIndex index) const
	{
		return this->elements[index];
	}

	//------------------------------------------------------------------------------
	/**
		The equality operator returns true if all elements are identical. The
		T class must support the equality operator.
	*/
	template<class T> bool
	Array<T>::operator==(const Array<T>& rhs) const
	{
		if (rhs.Size() == this->Size())
		{
			tIndex i;
			tSize num = this->Size();
			for (i = 0; i < num; i++)
			{
				if (!(this->elements[i] == rhs.elements[i]))
				{
					return false;
				}
			}
			return true;
		}
		else
		{
			return false;
		}
	}

	//------------------------------------------------------------------------------
	/**
		The inequality operator returns true if at least one element in the 
		array is different, or the array sizes are different.
	*/
	template<class T> bool
	Array<T>::operator!=(const Array<T>& rhs) const
	{
		return !(*this == rhs);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> T&
	Array<T>::Front() const
	{
		return this->elements[0];
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> T&
	Array<T>::Back() const
	{
		return this->elements[this->size - 1];
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> bool 
	Array<T>::IsEmpty() const
	{
		return (this->size == 0);
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::EraseIndex(tIndex index)
	{
		if (index == (this->size - 1))
		{
			// special case: last element
			this->Destroy(&(this->elements[index]));
			this->size--;
		}
		else
		{
			this->Move(index + 1, index);
		}
	}

	//------------------------------------------------------------------------------
	/**    
		NOTE: this method is fast but destroys the sorting order!
	*/
	template<class T> void
	Array<T>::EraseIndexSwap(tIndex index)
	{

		// swap with last element, and destroy last element
		tIndex lastElementIndex = this->size - 1;
		if (index < lastElementIndex)
		{
			this->elements[index] = this->elements[lastElementIndex];
		}
		this->Destroy(&(this->elements[lastElementIndex]));
		this->size--;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> typename Array<T>::Iterator
	Array<T>::Erase(typename Array<T>::Iterator iter)
	{
		this->EraseIndex(tIndex(iter - this->elements));
		return iter;
	}

	//------------------------------------------------------------------------------
	/**
		NOTE: this method is fast but destroys the sorting order!
	*/
	template<class T> typename Array<T>::Iterator
	Array<T>::EraseSwap(typename Array<T>::Iterator iter)
	{
		this->EraseSwapIndex(tIndex(iter - this->elements));
		return iter;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> void
	Array<T>::Insert(tIndex index, const T& elm)
	{
		if (index == this->size)
		{
			// special case: append element to back
			this->Add(elm);
		}
		else
		{
			this->Move(index, index + 1);
			this->elements[index] = elm;
		}
	}

	//------------------------------------------------------------------------------
	/**
		The current implementation of this method does not shrink the 
		preallocated space. It simply sets the array size to 0.
	*/
	template<class T> void
	Array<T>::Clear()
	{
		tIndex i;
		for (i = 0; i < this->size; i++)
		{
			this->Destroy(&(this->elements[i]));
		}
		this->size = 0;
	}

	//------------------------------------------------------------------------------
	/**
		This is identical with Clear(), but does NOT call destructors (it just
		resets the size member. USE WITH CARE!
	*/
	template<class T> void
	Array<T>::Reset()
	{
		this->size = 0;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> typename Array<T>::Iterator
	Array<T>::Begin() const
	{
		return this->elements;
	}

	//------------------------------------------------------------------------------
	/**
	*/
	template<class T> typename Array<T>::Iterator
	Array<T>::End() const
	{
		return this->elements + this->size;
	}

	//------------------------------------------------------------------------------
	/**
		Find element in array, return iterator, or 0 if element not
		found.

		@param  elm     element to find
		@return         element iterator, or 0 if not found
	*/
	template<class T> typename Array<T>::Iterator
	Array<T>::Find(const T& elm) const
	{
		tIndex index;
		for (index = 0; index < this->size; index++)
		{
			if (this->elements[index] == elm)
			{
				return &(this->elements[index]);
			}
		}
		return 0;
	}

	//------------------------------------------------------------------------------
	/**
		Find element in array, return element index, or InvalidIndex if element not
		found.

		@param  elm     element to find
		@return         index to element, or InvalidIndex if not found
	*/
	template<class T> tIndex
	Array<T>::FindIndex(const T& elm) const
	{
		tIndex index;
		for (index = 0; index < this->size; index++)
		{
			if (this->elements[index] == elm)
			{
				return index;
			}
		}
		return InvalidIndex;
	}

	//------------------------------------------------------------------------------
	/**
		Fills an array range with the given element value. Will grow the
		array if necessary

		@param  first   index of first element to start fill
		@param  num     num elements to fill
		@param  elm     fill value
	*/
	template<class T> void
	Array<T>::Fill(tIndex first, tSize num, const T& elm)
	{
		if ((first + num) > this->size)
		{
			this->GrowTo(first + num);
		}
		tIndex i;
		for (i = first; i < (first + num); i++)
		{
			this->elements[i] = elm;
		}
	}

	//------------------------------------------------------------------------------
	/**
		Returns a new array with all element which are in rhs, but not in this.
		Carefull, this method may be very slow with large arrays!

		@todo this method is broken, check test case to see why!
	*/
	template<class T> Array<T>
	Array<T>::Difference(const Array<T>& rhs)
	{
		Array<T> diff;
		tIndex i;
		tSize num = rhs.Size();
		for (i = 0; i < num; i++)
		{
			if (0 == this->Find(rhs[i]))
			{
				diff.Add(rhs[i]);
			}
		}
		return diff;
	}

	//------------------------------------------------------------------------------
	/**
		Sorts the array. This just calls the STL sort algorithm.
	*/
	template<class T> void
	Array<T>::Sort()
	{
		std::sort(this->Begin(), this->End());
	}

	//------------------------------------------------------------------------------
	/**
		Does a binary search on the array, returns the index of the identical
		element, or InvalidIndex if not found
	*/
	template<class T> tIndex
	Array<T>::BinarySearchIndex(const T& elm) const
	{
		tSize num = this->Size();
		if (num > 0)
		{
			tIndex half;
			tIndex lo = 0;
			tIndex hi = num - 1;
			tIndex mid;
			while (lo <= hi) 
			{
				if (0 != (half = num/2)) 
				{
					mid = lo + ((num & 1) ? half : (half - 1));
					if (elm < this->elements[mid])
					{
						hi = mid - 1;
						num = num & 1 ? half : half - 1;
					} 
					else if (elm > this->elements[mid]) 
					{
						lo = mid + 1;
						num = half;
					} 
					else
					{
						return mid;
					}
				} 
				else if (0 != num) 
				{
					if (elm != this->elements[lo])
					{
						return InvalidIndex;
					}
					else      
					{
						return lo;
					}
				} 
				else 
				{
					break;
				}
			}
		}
		return InvalidIndex;
	}

	//------------------------------------------------------------------------------
	/**
		This tests, whether the array is sorted. This is a slow operation
		O(n).
	*/
	template<class T> bool
	Array<T>::IsSorted() const
	{
		if (this->size > 1)
		{
			tIndex i;
			for (i = 0; i < this->size - 1; i++)
			{
				if (this->elements[i] > this->elements[i + 1])
				{
					return false;
				}
			}
		}
		return true;
	}

	//------------------------------------------------------------------------------
	/**
		This inserts an element at the end of a range of identical elements
		starting at a given index. Performance is O(n). Returns the index
		at which the element was added.
	*/
	template<class T> tIndex
	Array<T>::InsertAtEndOfIdenticalRange(tIndex startIndex, const T& elm)
	{
		tIndex i = startIndex + 1;
		for (; i < this->size; i++)
		{
			if (this->elements[i] != elm)
			{
				this->Insert(i, elm);
				return i;
			}
		}

		// fallthrough: new element needs to be appended to end
		this->Add(elm);
		return (this->Size() - 1);
	}

	//------------------------------------------------------------------------------
	/**
		This inserts the element into a sorted array. Returns the index
		at which the element was inserted.
	*/
	template<class T> tIndex
	Array<T>::InsertSorted(const T& elm)
	{
		tSize num = this->Size();
		if (num == 0)
		{
			// array is currently empty
			this->Add(elm);
			return this->Size() - 1;
		}
		else
		{
			tIndex half;
			tIndex lo = 0;
			tIndex hi = num - 1;
			tIndex mid;
			while (lo <= hi) 
			{
				if (0 != (half = num/2)) 
				{
					mid = lo + ((num & 1) ? half : (half - 1));
					if (elm < this->elements[mid])
					{
						hi = mid - 1;
						num = num & 1 ? half : half - 1;
					} 
					else if (elm > this->elements[mid]) 
					{
						lo = mid + 1;
						num = half;
					} 
					else
					{
						// element already exists at [mid], append the
						// new element to the end of the range
						return this->InsertAtEndOfIdenticalRange(mid, elm);
					}
				} 
				else if (0 != num) 
				{
					if (elm < this->elements[lo])
					{
						this->Insert(lo, elm);
						return lo;
					}
					else if (elm > this->elements[lo])
					{
						this->Insert(lo + 1, elm);
						return lo + 1;
					}
					else      
					{
						// element already exists at [low], append 
						// the new element to the end of the range
						return this->InsertAtEndOfIdenticalRange(lo, elm);
					}
				} 
				else 
				{
					this->Insert(lo, elm);
					return lo;
				}
			}
			if (elm < this->elements[lo])
			{
				this->Insert(lo, elm);
				return lo;
			}
			else if (elm > this->elements[lo])
			{
				this->Insert(lo + 1, elm);
				return lo + 1;
			}
			else
			{
				// can't happen(?)
			}
		}
		return InvalidIndex;
	}

}

#endif // array_h__